home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / theory / kohonen.ai < prev   
Encoding:
Text File  |  1994-12-06  |  5.2 KB  |  181 lines
  1. Newsgroups: rec.games.programmer
  2. From: jang@ecf.toronto.edu (JANG  HIN LANG)
  3. Subject: AI Learning Algorithms
  4. Date: Wed, 30 Nov 1994 22:45:40 GMT
  5.  
  6. I do not believe anyone discussed, in detail, on how to apply
  7. basic principles of articificial intelligence, neural computing 
  8. and machine learning into computer games.  In using the
  9. outdated Kohonen Algorithm (explained below) we can simulate
  10. an intelligent computer opponent that can learn from its 
  11. mistakes.
  12.  
  13.  
  14. For the interested few, here in my treatment on the subject.
  15.  
  16.  
  17. ---
  18.  
  19.  
  20. The least sophisticated of AI algorithms simluates the function
  21. of the biological neuron.  First proposed four decades ago, the
  22. outline of the basic model is as follows
  23.  
  24.  
  25.  
  26. dendrite                   |------------|
  27. (input) -----------------O |            |
  28.                            | cell body  | O---------------
  29.                            |            |          axon (output)
  30. (input) -----------------O |            |
  31.                            |------------|
  32.  
  33. where O is a synapse.
  34.  
  35. The synapse is not an actual physical linkage; instead it is a
  36. temporary chemical one that can vary over time.  To represent
  37. these variable connections in our computer model we assign a 
  38. multiplicative weight to each input pathway.  A high weight
  39. term denotes a favourable connection.  The cell body contains
  40. a predefined value known as the threshold.  An output signal
  41. wll be produced if the input to the neuron is greater than
  42. the threshold value.
  43.  
  44. We now require a mechanism that allows us the simulate learning
  45. in our perceptrons.
  46.  
  47. In biological systems, the process of learning is thought to 
  48. involve modifications in the effective coupling between neurons.
  49. In our computer model, we make small adjustments to the weights.
  50. To appreciate what this means, consider this learning paradigm:
  51.  
  52.     - set the weights w and thresholds t of perceptrons to
  53.       random values
  54.  
  55.     - present the input x(0), x(1), x(2), ...., x(n-1)
  56.  
  57.     - calculate the actual output by comparing the threshold
  58.       value and the weighted sum of the input
  59.  
  60.  
  61.             n - 1
  62.             -----
  63.     weighted sum =  \    w(i) * x(i)
  64.             /
  65.             -----
  66.             i = 0
  67.  
  68.     - alter the weights to reinforce correct decisions and 
  69.       discourage incorrect decisions.
  70.  
  71.  
  72. Adaptation of the learning paradigm lead to the development of 
  73. the Kohonen Network Algorithm, named after Professor T. Kohonen
  74. of the Faculty of Information Sciences at the University of
  75. Helsinki, Finland.  Instead of comparing input values to thresholds,
  76. (as in the case with perceptrons) Kohonen compared the weights of
  77. all output nodes and picked the set of nodes having weights that
  78. closely matched the magnitude of the input signal.
  79.  
  80.  
  81. NOTE: --->    the following algorithm may not be appropriate for
  82.         your particular application in terms of space
  83.         and time efficiency.  If you require information
  84.         regarding optimised AI learning algorithms consult
  85.         this reference:
  86.  
  87.         Kaelbling, Leslie Pack
  88.         Learning in Embedded Systems
  89.         The MIT Press, Cambridge, Massachusetts
  90.         (c) 1993
  91.         ISBN 0-262-11174-8
  92.  
  93.  
  94. The self-organising network consists of a matrix of output nodes j
  95. all of which are connected to every input node i.
  96.  
  97.  
  98.             ----------------
  99.             \  O    O    O    \
  100.              \         \
  101.     output nodes j      \  O    O    O  \
  102.                \           \
  103.                 \  O    O    O  \
  104.                  ----------------
  105.  
  106.  
  107.  
  108.     input nodes i        O    O
  109.  
  110.  
  111. The algorithm determines the "winning" node j* that closely matches
  112. the expected output as determined by the set of input nodes i.  
  113. Modifying the weights of j* and its neighbours will produce a
  114. set of desired outcomes.
  115.  
  116. Kohonen successfully implemented this technique for a speech
  117. recognition system in the mid 1980's.
  118.  
  119. -------------------------
  120. KOHONEN NETWORK ALGORITHM
  121. -------------------------
  122.  
  123.  
  124. 1. Initialise network
  125.     - define w(ij) (0 <= i <= n-1) to be the weight from input
  126.       node i to output node j.  Set the weights from the n 
  127.       inputs to some small values.  Set the initial radius
  128.       of the neighbourhood around node j, N(j), to some large
  129.       value.
  130.  
  131. 2. Present input
  132.     - present input x(0), x(1), x(2), .... , x(n-1) where x(i)
  133.       is the input to node i.
  134.  
  135. 3. Calculate distance
  136.     - compute distance d(j) between input node i and each output
  137.       node j as in
  138.  
  139.  
  140.             n - 1
  141.             -----
  142.         d(j) =  \    (x(i) - w(ij))^2
  143.             /
  144.             -----
  145.             i = 0
  146.  
  147. 4. Select minimum distance and denote output node j with minimum d(j)
  148.    to be j*.
  149.  
  150. 5. Update weights
  151.     - update weight for node j* and its neighbours as defined by
  152.       the extent of boundary N(j).
  153.  
  154.     
  155.         w(ij) = w(ij) + M * (x(i) - w(ij))
  156.  
  157.     The M term is used to control the rate of weight adjustment.
  158.     This value should be set in the range [0.5, 1] and then
  159.     gradually decreased in accordance to a linear function as
  160.     the number of learning cycles increases.
  161.  
  162. 6. If the expected solution set has not been found, repeat the
  163.    learning cycle (steps 2-5).
  164.  
  165. 7. The solution set S of the network is now a counter-strategy tactic
  166.    that a computer opponent can use against the player.
  167.  
  168.    If, for example, the network consists of 16 output nodes, four input
  169.    nodes and minimum neighbourhood size of four, the Kohonen Algorithm
  170.    can develop 216 (9 * 4!) unique strategy tactics.  Provided that
  171.    the network has been trained well, the computer opponent will be
  172.    rather challenging.
  173.  
  174.  
  175.  
  176. --------------------------------------------------------------------
  177.  
  178.  
  179.  
  180.  
  181.